package com.company.ljh.hard;
/**
 * 124.路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
 *
 * 路径和 是路径中各节点值的总和。
 *
 * 给你一个二叉树的根节点 root ，返回其 最大路径和
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/binary-tree-maximum-path-sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

import com.company.ljh.utils.TreeNode;

import java.util.Arrays;

/**
 * @description:
 * @projectName:leet_code
 * @see:com.company.ljh.hard
 * @author:ljh
 * @createTime:2022/6/10 16:22
 * @version:1.0
 */
public class 二叉树中的最大路径和 {
    int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        getValue(root);
        int result = max;
        max = Integer.MIN_VALUE;
        return result;
    }
    private int getValue(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftValue = getValue(root.left);
        int rightValue = getValue(root.right);
        //求当前节点的最大贡献值
        int rootValue = (Math.max(leftValue,rightValue) > 0?Math.max(leftValue,rightValue):0)+root.val;
        max = Math.max(root.val+(leftValue>0?leftValue:0)+(rightValue>0?rightValue:0),max);
        return rootValue;
    }
}
